#include <iostream>
#include "../head/heapSort.h"
#include "../head/SortTestHelper.h"
#include "../head/shellSort.h"
#include "../head/quickSort3Ways.h"
#include "../head/quickSort.h"
#include "../head/mergeSort.h"
#include "../head/indexMaxHeapSort.h"

using namespace std;
void testMaxHeap();
void countTime();
void test(int n);

int main(){
	countTime();
	/*
	test(4);
	cout << endl;
	test(3);
	cout << endl;
	test(2);
	cout << endl;
	test(1);
	cout << endl;
	*/
	return 0;
}

void testMaxHeap(){
	MaxHeap<int> maxHeap = MaxHeap<int>(100);
	cout << maxHeap.size() << endl;
	srand(time(NULL));
	for(int i = 0;i < 10; ++i)
		maxHeap.insert(rand()%100);	// [0,100) 随机数
	maxHeap.toString();

	while(!maxHeap.isEmpty()){
		cout << maxHeap.extractMax() << " ";
	}
	cout << endl;
}

void countTime(){
	// test
	int a[] = {9,8,7,6,5,4,3,2,1,0};
	indexMaxHeapSort(a, 10);
	SortTestHelper::printArray(a, 10);

	// countTime
	int n = 1000000;
	int *arr = SortTestHelper::generateRandomArray(n,0,n);
	// int *arr = SortTestHelper::generateNearlyOrderedArray(n,100);

	int *arr1 = SortTestHelper::copyIntArray(arr, n);
	int *arr2 = SortTestHelper::copyIntArray(arr, n);
	int *arr3 = SortTestHelper::copyIntArray(arr, n);
	int *arr4 = SortTestHelper::copyIntArray(arr, n);
	int *arr5 = SortTestHelper::copyIntArray(arr, n);
	int *arr6 = SortTestHelper::copyIntArray(arr, n);
	int *arr7 = SortTestHelper::copyIntArray(arr, n);
	
	SortTestHelper::testSort("heapSort1   Sort ", heapSort1,arr,n);
	SortTestHelper::testSort("shell       Sort ", shellSort,arr1,n);
	SortTestHelper::testSort("quick       Sort ", quickSort,arr2,n);
	SortTestHelper::testSort("merge       Sort ", mergeSort,arr3,n);
	SortTestHelper::testSort("heapSort2   Sort ", heapSort2,arr4,n);
	SortTestHelper::testSort("quickSort3Way    ", quickSort3Ways,arr5,n);
	SortTestHelper::testSort("heap        Sort ", heapSort,arr6,n);
	SortTestHelper::testSort("indexMaxHeapSort ", indexMaxHeapSort,arr7,n);

	delete[] arr;
	delete[] arr1;
	delete[] arr2;
	delete[] arr3;
	delete[] arr4;
	delete[] arr5;
	delete[] arr6;
	delete[] arr7;
}

void test(int n){
	if(n > 0){
		cout << n << " \t";
		test(n - 1);
		 test(n - 2);
	}
}
